{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 施磊: C++代码应用实践-海量数据求top k问题解决方案汇总"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 海量数据查重与 TopK 综合解决方案整理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "问题场景概述\n",
    "\n",
    "- **目标一：** 在 20 万个随机整数中找到重复次数最多的前 10 个数字（TopK + 查重组合问题）。\n",
    "- **目标二：** 在内存受限（如 200 MB/400 MB）的条件下处理 10 亿～50 亿规模整数文件，统计重复元素及其出现次数。\n",
    "- **延展需求：** 多文件重复元素交集、字符串查重、仅判断是否重复等。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **TopK + 查重组合问题** 核心在于：哈希统计频次 + 小根堆维护 TopK。\n",
    "- **内存受限的大数据场景** 必须引入 **分治/分片** 思路，结合本地或分布式计算。\n",
    "- **多种数据结构与算法** 各有适用范围，需根据数据类型、可用内存、实时性要求做取舍。\n",
    "- **实践环节** 强调完整实现、细致调试、合理规划文件与内存资源，以确保处理海量数据时的稳定性与效率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "多种查重技术路线对比\n",
    "\n",
    "| 方法           | 核心思想                    | 优势                             | 局限                            | 场景                     |\n",
    "| -------------- | --------------------------- | -------------------------------- | ------------------------------- | ------------------------ |\n",
    "| 哈希表         | `unordered_set/map`         | 操作 O(1)，实现简单              | 内存占用高（50 亿整数约 40 GB） | 内存充足、数据量适中     |\n",
    "| 分治 + 哈希表  | 分片到小文件后逐个处理      | 破除内存瓶颈，可分布式/并行      | 需额外 I/O，管理复杂            | 超大规模整数、分布式场景 |\n",
    "| 布隆过滤器     | 位图 + 多哈希函数           | 空间效率高                       | 存在假阳性，无法统计次数        | 仅需判断“是否出现过”     |\n",
    "| Trie（字典树） | 前缀树共享字符串公共前缀    | 字符串查重、前缀查询高效         | 构建复杂，指针开销大            | URL、敏感词、输入法索引  |\n",
    "| 快速选择/分割  | `nth_element`、partition    | 平均 O(n)，可一次性得到 TopK/第K | 最坏 O(n²)，会重排原序列        | 静态数组、可修改数据场景 |\n",
    "| 小根堆         | `priority_queue` 自定义比较 | O(n log K)，适合数据流           | 需要额外 K 规模空间             | 在线/流式 TopK           |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TopK 求解方法比较\n",
    "\n",
    "| 场景                       | 推荐方法                | 理由                                        |\n",
    "| -------------------------- | ----------------------- | ------------------------------------------- |\n",
    "| 在线/流式数据              | 小根堆（TopK 大）       | 只需维护 K 个元素，O(n log K)。             |\n",
    "| 静态数组、可修改           | `nth_element`/partition | 平均 O(n)，一次性获取第 K 或 TopK。         |\n",
    "| 需要 TopK 小的元素         | 大根堆 + 容量 K         | 维护当前最大的 K 个，堆顶即最大，方便淘汰。 |\n",
    "| 需要第 K 个（排名）        | 快速选择                | 分割后基准位置直接对应排名。                |\n",
    "| 数据几乎有序或最坏情况敏感 | 堆方法                  | 时间复杂度稳定，不受输入分布影响。          |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 哈希统计 + 小根堆：TopK 频次问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "核心思路\n",
    "\n",
    "| 步骤      | 说明                                                         |\n",
    "| --------- | ------------------------------------------------------------ |\n",
    "| 哈希计数  | 使用 `unordered_map<int,int>` 统计每个数字出现次数。         |\n",
    "| TopK 维护 | 使用容量为 K 的小根堆（priority_queue + 自定义比较器）保存当前 TopK。 |\n",
    "| 替换规则  | 遍历哈希表。当新元素频次 > 堆顶（最小频次）时，弹出堆顶、插入新元素。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "实现要点\n",
    "\n",
    "- **哈希插入逻辑：** `++freq[val]`；若键不存在，会自动插入并初始化为 0。\n",
    "- **小根堆构建：**\n",
    "  - 元素类型：`std::pair<int,int>`（{数字, 频次}）。\n",
    "  - 比较器：`return a.second > b.second;` 使 `priority_queue` 变为小根堆。\n",
    "- **初始化阶段：** 先将哈希表中任意 K 个元素压入堆中。\n",
    "- **时间 & 空间复杂度：** 哈希统计 O(n)，堆维护 O(n log K)，空间 O(n)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "边界与优化\n",
    "\n",
    "- **重复元素不足 K 个：** 堆中可能出现频次=1 的元素，按需求决定是否过滤。\n",
    "- **替代方案：**\n",
    "  - `std::nth_element` 或 `std::partial_sort` 在将 map 转为 vector 后筛选 TopK，平均 O(n)，最坏 O(n²)。\n",
    "  - 更适合静态数据且可接受修改容器内容的场景。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 海量数据文件分片处理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "“哈希映射 + 哈希统计 + TopK” 三段式\n",
    "\n",
    "1. **哈希映射分片：** 使用除留余数法 `idx = value % FILE_NO` 将大文件拆成多个小文件。\n",
    "   - `FILE_NO` 取素数（如 11、27、127）以减少碰撞。\n",
    "   - 保证相同元素落入同一个分片文件。\n",
    "2. **单分片处理：** 对每个小文件加载内存，使用哈希表统计频次。\n",
    "3. **TopK 汇总：** 对每个分片输出 TopK，再合并或统一处理得到全局 TopK。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关键细节\n",
    "\n",
    "- **文件操作：** `fopen(\"wb+\")` 创建文件，`FILE* pfile[FILE_NO]` 管理句柄，写后需 `fseek(fp, 0, SEEK_SET)` 重置。\n",
    "- **测试数据生成：** 随机生成（如 2 万个整数）写入二进制文件，便于功能验证。\n",
    "- **错误处理：** 关闭 VS 的 SDL 安全检查仅为演示；生产代码需保留安全机制。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "性能与资源\n",
    "\n",
    "- 示例：10 亿整数 / 200 MB 内存\n",
    "  - 单个分片 ≈ 200 MB ⇒ 需至少 11 个小文件。\n",
    "- 示例：50 亿整数 / 400 MB 内存\n",
    "  - 数据约 20 GB，若按 160 MB 分片 ⇒ 至少 127 个小文件。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 单文件与多文件查重案例"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "单文件（50 亿整数，内存 400 MB）\n",
    "\n",
    "1. 计算可容纳元素数量，确定分片数量（≈ 120 个）。\n",
    "2. 利用哈希映射函数将元素写入对应小文件（保证相同元素同分片）。\n",
    "3. 对每个小文件建立哈希表统计频次，输出/合并结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "双文件（各 10 亿整数，内存 400 MB）\n",
    "\n",
    "1. 为两个源文件各划分同样数量的小文件（如 27 对 `a_i.txt`/`b_i.txt`）。\n",
    "2. 读取 `a_i.txt` 数据建立哈希表；再逐条读取 `b_i.txt` 查询并统计交集元素。\n",
    "3. 输出每对小文件的重复元素及次数。\n",
    "\n",
    "> **关键性质：** 同样的哈希映射保证相同元素必定处于同编号小文件中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 实战建议与注意事项\n",
    "\n",
    "1. **内存评估：** 统计对象的总大小 + 哈希表装载因子，提前预估是否超限。\n",
    "2. **分片策略：**\n",
    "   - 素数分片数减少冲突。\n",
    "   - 分片大小 ≈ 内存容量留出安全余量。\n",
    "3. **编码实践：**\n",
    "   - 建议手写完整流程（文件读写、哈希统计、堆/排序筛选），强化调试能力。\n",
    "   - 留意资源释放（`fclose`、异常处理）。\n",
    "4. **调试技巧：** 使用 IDE 调试器（如 VS 本地调试器）逐步验证读取、哈希、堆操作。\n",
    "5. **扩展工具：**\n",
    "   - 允许误判时，可引入布隆过滤器作为快速预筛。\n",
    "   - 字符串场景下可采用 Trie 结合哈希实现混合策略。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
